\section{Problema 1}

\subsection{Introducci\'on}

En este ejercicio debíamos calcular cuánto cargamento máximo podría llevar un camión entre dos ciudades específicas. Recibíamos como entrada esas dos ciudades más las rutas; las cuales unían dos ciudades y especificaban el cargamento máximo que podría llevar el camión si transita por esta ruta. En otras palabras, debíamos buscar un camino entre la ciudad origen y la ciudad destino de tal modo que la \textit{ruta  con peso mínimo} perteneciente a este camino sea mayor que cualquier \textit{ruta  con peso mínimo} de los demás caminos existentes entre ambas ciudades. Dado este camino, devolver su \textbf{ruta con peso mínimo}.



	   
\subsection{Desarrollo}

Si vemos a cada ciudad por la que tiene que pasar el camionero como un nodo de un grafo y a cada camino que une a dos ciudades como un eje estaríamos viendo que el problema del camionero se puede modelar como un grafo ponderado, en el cual la ponderación de los ejes entre 2 ciudades sería el peso maximo soportado por el camino entre esas dos ciudades.

Como el camionero quiere viajar con la mayor cantidad de peso posible desde la ciudad origen hacia la ciudad destino, nuestro problema se puede plantear como \textit{encontrar el árbol generador maximo del grafo}. Éste nuevo árbol contiene al camino simple entre dos nodos cualquiera, tal que la arista de peso mínimo de este camino es máxima entre todas las aristas de peso mínimo de los otros caminos entre los mismos pares de nodos. Más de esto en la sección Demostración.

Para resolver el problema planteando anteriormente vamos a implementar el algoritmo de Kruskal que se va a encargar de armar el arbol generador máximo. Comparando al algoritmo de Kruskal que normalmente se utiliza en la práctica que busca al árbol generador mínimo, el que nosotros usamos buca, en cambio, al árbol generador máximo que en vez de recibir ordenados los ejes por menor peso los recibe ordenados por mayor peso. Esto lo que hace es que al ir tomando ejes de lista ordenada nos vayamos quedando con los ejes de \textbf{mayor} peso y al encontrar los primeros n-1 ejes que no formen ciclos entre si (considerando n la cantidad total de ciudades o nodos) habremos conseguido el árbol generador maximo.

Una vez que tenemos los ejes que conforman al árbol generador maximo se los vamos a pasar a la función \textit{calcular\_peso\_camino\_máximo} junto con la cantidad total de nodos y junto con los nodos origen y destino para que luego ésta nos devuelva el peso máximo que puede llevar el camion desde la ciudad origen a la ciudad destino en todo el grafo de la siguiente forma: la función se encarga de armar un \textit{arreglo de adyacencias} con la lista de ejes del árbol generador maximo. Lo nombramos de esta manera al arreglo ya que está armado de tal forma que si vamos a la posición \textit{i} del arreglo obtenemos la lista de nodos adyacentes al nodo \textit{i}.

Una vez armado el arreglo llama a la función \textit{calcular\_peso} que, en resumidas palabras, recorre el árbol generador maximo revisando los ejes del arreglo comenzando desde el nodo origen (ciudad desde la cual parte el camionero) hasta llegar al nodo destino. Luego ,una vez encontrado el camino hasta destino, vuelve por los ejes (ejes del camino que va del origen a destino en el árbol generador maximo) guardándose el peso del eje menos pesado del camino. Finaliza cuando el algoritmo vuelve al nodo origen habiendo recorriendo los ejes y se obtiene el peso mínimo del camino entre \textbf{p} y \textbf{q}, origen y destino respectivamente, que sería la solución al problema del camionero.  

Como en nuestro enfoque debíamos encontrar el árbol generador máximo, teníamos dos opciones: usar Prim o usar Kruskal. Aunque Prim es preferible para los grafos con muchos ejes (gafos \textit{densos}) y Kruskal para los grafos con pocos ejes (grafos \textit{dispersos}) y \textit{normalmente}, en el mundo físico, cada ciudad no está unida por una ruta con todas las otras ciudades sino que se trata de que sea lo menor denso posible la cantidad de rutas similando un árbol, esto no hubiera hecho mucha diferencia en este problemapor lo siguiente: Como dijimos antes, Kruskal es mejor para los grafos dispersos y \textit{normalmente} se trata de minimizar la cantidad de rutas en un territorio por razones obvias (pensar un minuto el caso en que las rutas y las ciudades formen un grafo completo en la realidad), entonces uno estaría inclinado a decir que Kruskal es mejor para este problema que Prim. Pero hay una diferencia, que es que en Prim podemos ir encontrando la solución mientras vamos iterando los nodos. En cambio, en Kruskal no se nos ocurrió manera de hacer algo parecido y en cambio debimos iterar los nodos del árbol generador máximo resultante para obtener la solución requerida. Esto agrega una complejidad asintóticamente despreciable a usar Kruskal pero haría la diferencia entre Prim y éste ya que Prim obtendría la solución directamente. Si vamos al caso, es una diferencia constante pero siempre lo fue en la guerra entre Prim y Kruskal.




%
%Nuestro algoritmo sigue la filosofía del \textit{BFS} de recorrer el grafo a lo ancho, o sea, lo va recorriendo de a ``niveles'' en vez de recorrer sin frenar hasta no poder más y despu\'es volver (como hace el DFS). Lo que modificamos nosotros fue que nuestro algoritmo cuando la iteraci\'on est\'a en un v\'ertice, numera a los vecinos (o ``hijos'') del vértice asignándoles uno más que su número. De esta forma, dado un vértice podemos calcular su distancia al resto. El algoritmo arranca con distancia 0 en el vértice inicial e infinito en el resto y va calculando las distancias en base al inicial.
%
%A primera vista no se ve la relaci\'on entre BFS y este problema, pero mirémoslo como si fuera un Grafo en el cual cada amistad es un eje y cada investigador un v\'ertice y existe una relación de amistad entre 2 investigadores \textit{x} e \textit{y} si y sólo si existe un camino entre los vértices del grafo que representan a \textit{x} y a \textit{y}. Nos piden buscar \textit{la cantidad de veces que el entusiasmo original se verá fraccionado al 50\%} o devolver \textit{0} si no hay relación de amistad. Al explicar que en \textit{todo investigador [que no sea p] se genera un riguroso 50\% de la sensación de la más entusiasmada de sus amistades directas} nos están diciendo básicamente que mientras más larga sea la ``longitud del camino de amistad \textit{mínima}'', más fraccionado estará el entusiasmo original. Como puede haber más de un ``camino de amistades'' entre dos investigadores, debemos buscar el de longitud mínima. O sea, el de menor cantidad de ejes (amistades) entre \textit{p} y \textit{q}. Eso 
% es exactamente lo que hace nuestro algoritmo modificado de BFS.
%\begin{center}
%    \begin{tabular}{ | p{17cm} |}
%	\hline 	\\ 
%	 Entonces, el procedimiento sería el siguiente:
%	\begin{compactenum}
%		\item Aplicar una función biyectiva a los investigadores para identificarlos uno con uno con un vértice en el grafo. La vuelta también es posible de así requerirlo (de vértice en el grafo a nombre de investigador).
%		\item Generar el grafo con sus vértices y ejes de tal manera que se pueda buscar en tiempo constante los vértices adyacentes a un vértice dado. Si dos investigadores son amigos sus respectivos vértices son adyacentes en el grafo y viceversa.
%		\item Aplicar el algoritmo de BFS-modificado al grafo generado.
%		\item Devolver la solución
%	\end{compactenum}
%	\\ \hline
%    \end{tabular}
%\end{center}
%En el punto 1, por la forma que hicimos la funci\'on biyectiva, dado un \textit{vértice} podemos obtener su respectivo \textit{string} (nombre del investigador)  en tiempo constante. En cambio, la vuelta no es tan simple. Obtenemos el \textit{vértice} relacionado con un \textit{string} dado con complejidad igual a \textit{cantidad de investigadores} (tomando como constante a la comparación entre strings). De \textit{vértice} a \textit{string} tenemos un arreglo donde la \textit{i}-ésima posición representa al vértice \textit{i} del grafo y contiene el string respectivo. Para la vuelta (de \textit{string} a \textit{vértice}) recorremos el arreglo buscando la posición de éste que tenga el string buscado.
%
%En el punto 2 la parte más importante de nuestra estructura es un \textit{vector} (o \textit{arreglo}) en el cual cada posición del vector representa a un vértice distinto y el contenido de cada una es una lista de los los vértices adyacentes al vértice representado por esta posición. De esta forma tenemos acceso aleatorio de tiempo constante a los adyacentes de cualquier vértice dado.
%
%Los puntos 1 y 2 pertenecerían al constructor del grafo y el 3 a la función ``BFS-mod''.
%
%
%\newpage
%
\subsection{Pseudoc\'odigo}
En el archivo \textbf{Kruskal.java} podremos encontrar la clase ``Kruskal'' con las funciones \textit{Kruskal} y las diferentes operaciones de \textbf{Disjoint Sets}. En el archivo \textbf{Ej1.java} podremos encontrar la clase ``Ej1'' con la función principal que orquesta la leída, la ejecución y la escritura de la solución del problema.\\
Resumen del Algoritmo:
\begin{compactenum}
	\item Leer de la entrada el origen y el destino; y la lista de adyacencias (las rutas).
	\item Pasar la lista de strings y peso a lista de IDs (enteros) y peso. Ordenarla en orden descendente.
	\item Generar el árbol generador máximo en base a la lista generada.
	\item Buscar la cantidad máxima de mercadería a transportar en base al grafo generador máximo y el origen y el destino.
\end{compactenum} \ \\
Variables y funciones globales:
\begin{compactitem}
	\item \textbf{padre(x)}: es una operación que usaremos sobre los \textbf{disjoint sets} que dado un vértice nos devuelve su ``padre''. En realidad sería más correcto llamarlo como \textbf{ancestro}  antes que padre ya que como usamos la implementación con \textit{path-compression}, cada vez que hacemos un FIND-SET(x) el árbol se auto-actualiza y deja de apuntar a su padre y queda apuntando al ``padre mayor''. \footnote{Sección 21.3(Disjoint-set forests) del libro ``Introduction to Algorithms'', 3rd edition. }
	\item \textbf{rank(x)}: otra operación que usaremos sobre los \textit{disjoint sets} pero ahora para decidir en la operación UNION-SET a cuál de los dos sets pasados como parámetros asignar como \textit{superior} o \textit{padre}. 
	\item \textbf{m}: la cantidad de rutas
	\item \textbf{n}: la cantidad de ciudades
	\item \textbf{peso\_global}: es una variable de entero global en la que iremos guardando el resultado parcial en los algoritmos calcular\_peso\_camino\_maximo y calcular\_peso
\end{compactitem}



\begin{parr}
\begin{algorithm}[H]
\caption{\operL{mapearAVértices}{ \vin{l}{lista de rutas}}{lista de ejes}}
\begin{algorithmic}[1]\parskip=1mm
\STATE \COMMENT{Cada eje sabe sus ambos vértices y su peso}
\STATE \COMMENT{Implementamos al set como un AVL ordenado de forma lexicográfica por su componente \textit{string}}
\STATE \COMMENT{y al agregar un elemento revisa antes si ya estaba}
\STATE \textbf{var} res $\leftarrow$ vector de ejes
\STATE \textbf{var} set $\leftarrow$ conjunto de elementos del tipo $<$string,ID$>$
\FOR{todas las rutas \textit{a} de \textit{l}}
	\STATE \textbf{var} \textit{tupla$_1$} $\leftarrow$ $1^{\circ}$ ciudad de \textit{a} como string y el número \textbf{-1} como ID
	\STATE \textbf{var} \textit{tupla$_2$} $\leftarrow$ $2^{\circ}$ ciudad de \textit{a} como string y el número \textbf{-1} como ID
	\STATE agregar \textit{tupla$_1$} y \textit{tupla$_2$} a \textit{set} 
\ENDFOR
\STATE \COMMENT{En \textit{set} ya tengo el conjunto total de tupla de ciudades sin repetir}
\STATE asignarle un ID diferente a cada elemento de \textit{set} recorriéndolos uno por uno
\FOR{todas las rutas \textit{a} de \textit{l}}
	\STATE \textbf{var} id$_1$ $\leftarrow$ buscar en \textit{set} la $1^{\circ}$ ciudad de \textbf{a} y devolver su ID
	\STATE \textbf{var} id$_2$ $\leftarrow$ buscar en \textit{set} la $2^{\circ}$ ciudad de \textbf{a} y devolver su ID
	\STATE agregar a \textit{res} el eje compuesto por ambos \textit{id}'s y el peso de \textit{a}
\ENDFOR
\STATE Ordenar al vector \textit{res} en orden descendente
\STATE \textbf{return} res
\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item for líneas 5-9: itera m veces y agregar al set tarda O(log $\vert$set$\vert$) (línea 8), entonces: $O\left(m * log(n)\right)$
	\item lineas 11: itera n elementos  y asigna en tiempo O(1) a cada uno:  $O\left(n\right)$
	\item for lineas 12-16: líneas 13-14 tiempo O(log(n)) cada una ya que busca en \textit{set} el elemento con esa ciudad como \textit{string} y el \textit{set} está ordenado lexicograficamente. Agregar el eje al set O(1) ya que es un eje compuesto por simples enteros. El for itera m veces entonces: $O\left(m * log\, n\right)$
	\item linea 18: como long(res) = m, ordenar el vector toma tiempo O(m*log m) y como m es como mucho del orden n$^2$,
	\begin{center}
	 {O(m*log m)} $\subseteq$ O(m*log n$^2$) $\subseteq$ O(m*2*log n) $\subseteq$ O(m*log n)
	\end{center}
	\item Complejidad final: $O\left(m * log\, n\right)$
\end{compactitem}
\end{algorithm}


% \begin{algorithm}[H]
% \caption{\operL{Prim-mod}{ \vin{G}{Grafo}, \vin{i}{vértice inicial}, \vin{d}{vértice destino} }{árbol generador máximo}}
% \begin{algorithmic}[1]\parskip=1mm
% \STATE \COMMENT{Q es una cola de prioridad máxima de tuplas en la cual comparamos si una tupla es mayor a otra si su segunda componente es mayor a la de la otra}
% 	\STATE \textbf{var} llave $\leftarrow$ arreglo de int que usaremos para la cola Q
% 	 \STATE \textbf{var} Q $\leftarrow$ cola de prioridad de tupla$<$vértice,int$>$ con el órden dado por int
% 	 \STATE \textbf{var} padre $\leftarrow$ arreglo que indica el padre de cada vértice en el árbol generador resultante
% 	 \FOR{cada u de los vértices de G}
% 	 	\STATE llave[u] $\leftarrow$ INFINITO
% 	 	\STATE padre[u] $\leftarrow$ VACÍO
% 	 	\STATE agregar a la cola Q la tupla $<$u,llave[u]$>$
% 	 \ENDFOR
% 	 \STATE llave[i] $\leftarrow$ 0 
% 	 \WHILE{Q no sea vacío}
% 		\STATE \textbf{var} u $\leftarrow$ extraer mínimo de Q
% 		\FOR{cada v adyacente a u}
% 			\IF{v pertenece a Q y peso(u,v)$<$llave[v]}
% 				\STATE padre[v] $\leftarrow$ u
% 				\STATE llave[v] $\leftarrow$ peso(u,v)
% 				\STATE actualizar Q con el nuevo peso de v
% 				\IF{v es el vértice destino (d)}
% 					\STATE salir del while y terminar
% 					\STATE \COMMENT{que termine porque ya conseguí el camino máximo entre \textit{i} y \textit{d}}
% 				\ENDIF
% 			\ENDIF
% 		\ENDFOR
% 	\ENDWHILE
% \end{algorithmic}
% Complejidades:
% \begin{compactitem}
% 	\item líneas 1:
% \end{compactitem}
% \end{algorithm}

% 
\begin{algorithm}[H]
\caption{\operL{Kruskal-mod}{ \vin{list}{lista de ejes}, \vin{n}{cantidad de vértices} }{árbol generador máximo}}
\begin{algorithmic}[1]\parskip=1mm
  \STATE \COMMENT{A es el árbol generador máximo resultante.}
  \STATE \COMMENT{la lista \textit{list} viene ordenada de mayor a menor según el campo peso de los ejes}
  \STATE \textbf{var} A $\leftarrow \emptyset $ 
  \FOR{cada vértice \textit{v} entre \texttt{0} y \texttt{n-1} }
    \STATE MAKE-SET(\textit{v})
  \ENDFOR
  \FOR{cada eje (\textit{u},\textit{v}) $\in$ \textit{list}}
    \IF{FIND-SET(\textit{u}) $\neq$ FIND-SET(\textit{v})}
      \STATE A $\leftarrow$ A $\cup$ {(\textit{u},\textit{v})}
      \STATE UNION-SET(\textit{u},\textit{v})
    \ENDIF
  \ENDFOR
  \STATE \textbf{return} A
\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item ya que es la implementación de Kruskal usando disjoint forests y sin ordenar la lista porque ya viene ordenada, como vimos en clase su complejidad es: O(m $\alpha$(n))
\end{compactitem}
\end{algorithm}

\begin{algorithm}[H]
\caption{\operL{FIND-SET}{ \vin{x}{vertice}}{vértice}}
\begin{algorithmic}[1]\parskip=1mm
  \STATE \COMMENT{padre(x) es una operación que dado un vértice nos devuelve en tiempo constante su ``padre''}
  \STATE \COMMENT{En el código la implementamos como un arreglo de ints para el uso de Kruskal}
  \IF{ padre(x) $\neq$ x }
    \STATE padre(x) $\leftarrow$ FIND-SET(padre(x))
  \ENDIF
  \STATE \textbf{return} padre(x)
\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item Complejidad: O($\alpha$(n)) por lo visto en clase de disjoint forests.
\end{compactitem}
\end{algorithm}
% 
\begin{algorithm}[H]
\caption{\operMA{UNION-SET}{ \vin{x}{vertice}, \vin{y}{vertice}} }
\begin{algorithmic}[1]\parskip=1mm
  \STATE \COMMENT{rank(x) es una operación que dado un vértice nos devuelve en tiempo constante su ``rango''}
  \STATE \COMMENT{En el código la implementamos como un arreglo de ints para el uso de Kruskal}
  \IF{ rank(x) $>$ rank(y) }
    \STATE padre(y) $\leftarrow$ x
  \ELSE
    \STATE padre(x) $\leftarrow$ y
  \ENDIF
  \IF{ rank(x) $=$ rank(y) }
    \STATE rank(y) $\leftarrow$ rank(y) +1
  \ENDIF
\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item Complejidad: todo O(1)
\end{compactitem}
\end{algorithm}
% 
\begin{algorithm}[H]
\caption{\operMA{MAKE-SET}{ \vin{x}{vertice}} }
\begin{algorithmic}[1]\parskip=1mm
  \STATE rango(x) $\leftarrow$ 0
  \STATE padre(x) $\leftarrow$ x
\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item Complejidad: todo O(1)
\end{compactitem}
\end{algorithm}


\begin{algorithm}[H]
\caption{\operMA{calcular\_peso\_camino\_maximo}{ \vin{n}{int}, \vin{ejes}{LinkedList$<$Eje$>$}, \vin{origen}{Integer}, \vin{destino}{Integer}}}
\begin{algorithmic}[1]\parskip=1mm
 \REQUIRE  \ 
 \begin{compactitem}
           \item \textit{n} es la cantidad de vértices
           \item \textit{ejes} la lista de ejes del AG
           \item \textit{origen} el nodo del cual quiero partir y destino el nodo a donde quiero llegar para calcular el peso del eje menos pesado
 \end{compactitem}
%  \STATE \COMMENT{Sea n la cantidad de vertices, , origen el nodo del cual quiero partir y destino el nodo a donde quiero llegar para calcular el peso del eje menos pesado.} 
 \STATE \textit{arrayEjes} $\leftarrow$ LinkedList[\textit{n}]
 \FOR {todo \textit{eje} de la lista \textit{ejes}}
 \STATE \textit{arrayEjes}[\textit{eje}.destino]  $\leftarrow$ \textit{eje}
 \STATE	\textit{arrayEjes}[\textit{eje}.origen]  $\leftarrow$ \textit{eje}
 \ENDFOR
 \STATE calcular\_peso(\textit{n}, \textit{arrayEjes}, \textit{origen}, \textit{destino}, -1);
 \STATE \COMMENT{calcular\_peso se guarda el \textit{peso} en una variable, que sería la respuesta al problema, para ser pedido cuando se lo requiera}
\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item Crear el Arreglo y rellenarlo de listas vacias tiene complejidad O(n).
	\item Recorrer los ejes y asignarlos al array tiene complejidad O(\#ejes). Esto igualmente lo podemos acotar por  O(n) ya que la lista ejes tiene el tamaño de un AGM ( n$-$1 ).
	\item La función calcular\_peso tiene complejidad O(n).
	\item Complejidad final O(n).
\end{compactitem}
\end{algorithm}

%

\begin{algorithm}[H]
\caption{\operMA{calcular\_peso}{ \vin{n}{int}, \vin{arrayEjes}{LinkedList$<$Eje$>$[]}, \vin{nodoActual}{Integer}, \vin{destino}{Integer}, \vin{nodoDeDondeVengo}{Integer}}}
 \LinesNumbered
 \SetAlgoLined
 \KwData{\begin{compactitem}
	   \item \textit{peso\_global} la variable global donde iremos guardando el resultado temporal del problema
           \item \textit{n} es la cantidad de vértices
           \item \textit{arrayEjes} un array de listas de ejes (en la i-esima posición del arreglo tiene los ejes que van del i-esimo vertice a los restantes del AG)
           \item \textit{nodoActual} es el nodo para el cual yo voy a recorrer sus ejes en este paso de la recursión
           \item \textit{destino} el vértice al cual quiero llegar recorriendo el AG para luego calcular el peso y nodoDeDondeVengo es el nodo de donde proviene el nodoActual (sirve para que en la recursión no vuelva por el eje que conecta a nodoActual con nodoDeDondeVengo)
 \end{compactitem}}
\For{\textnormal{cada} eje $\in$ arrayEjes\textnormal{[}nodoActual\textnormal{]}}{
    \If{eje \textnormal{no se conecta con el nodo} nodoDeDondeVengo}{
      \If{eje \textnormal{se conecta con el nodo} destino}{
	  peso\_global $\leftarrow$ peso de \textit{eje}\; \\
	  \textbf{return} true\; \\
      }
      \eIf{\textnormal{el campo} origen \textnormal{de} eje \textnormal{es el} nodoActual}{
	      \If{\textnormal{calcular\_peso(\textit{n}, \textit{arrayEjes}, \textit{eje}.destino, \textit{destino}, \textit{nodoActual})}}{
		  \If{\textnormal{peso\_global $>$ peso(\textit{eje})}}{
		    peso\_global $\leftarrow$ peso(\textit{eje})
		  }
		  \textbf{return} true \; \\
	      }
      }{
	\If{\textnormal{calcular\_peso(\textit{n}, \textit{arrayEjes}, \textit{eje}.origen, \textit{destino}, \textit{nodoActual})}}{
		  \If{\textnormal{peso\_global $>$ peso(\textit{eje})}}{
		    peso\_global $\leftarrow$ peso(\textit{eje})
		  }
		  \textbf{return} true \\
	}
      }
     }
    }
    \textbf{return} false
    Complejidades:
\begin{compactitem}
	\item Todas las asignaciones y comparaciones son O(1).
	\item La cantidad total de veces que se va a ingresar al for en la totalidad de las llamadas recursivas tiene complejidad O(n). A esto lo explicamos más detalladamente en la sección complejidad.
	%\item La cantidad de veces que se ingresa al for es la cantidad de ejes que van del nodoActual hacia otros nodos. Esta cantidad de ejes es como maximo n-1 ya que es la cantidad de ejes necesarios en un grafo de n vertics para formar un arbol generador. Esto se debe a que no llamamos recursivamente sobre el eje del cual venimos (lo evitamos sabiendo el nodoDeDondeVengo) y como no hay ciclos no vamos a recorrer ejes ya recorridos con anterioridad. Vale aclarar que en cada llamada recursiva sobre otro nodo se van a revisar todos los ejes que conectan a este nodo con otros y esto va a incluir al nodo de donde vengo. Finalmente si hago una llamada recursiva por cada nodo (en realidad si tengo n nodos, la cantidad maxima de llamadas es n-2 porque una vez que estoy en un nodo que se conecta con el nodo destino no vuelvo a hacer recursion sobre el nodo destino) voy a estar revisando cada uno de sus ejes que lo conectan con otro nodo
	\item Complejidad final O(n) (Se considera necesario que los ejes que se encuentran en el arreglo formen un Árbol generador ya que en caso contrario la función recursiva no termina) .
\end{compactitem}
\end{algorithm}
% 
% \begin{algorithm}[H]
% \caption{\operMA{calcular\_peso}{ \vin{n}{int}, \vin{arrayEjes}{LinkedList$<$Eje$>$[]}, \vin{nodoActual}{Integer}, \vin{destino}{Integer}, \vin{nodoDeDondeVengo}{Integer}}}
% \begin{algorithmic}[1]\parskip=1mm
%  \REQUIRE  \ 
%  \begin{compactitem}
%            \item \textit{n} es la cantidad de vértices
%            \item \textit{arrayEjes} un array de listas de ejes (en la i-esima posición del arreglo tiene los ejes que van del i-esimo vertice a los restantes del AG)
%            \item \textit{nodoActual} es el nodo para el cual yo voy a recorrer sus ejes en este paso de la recursión
%            \item \textit{destino} el vértice al cual quiero llegar recorriendo el AG para luego calcular el peso y nodoDeDondeVengo es el nodo de donde proviene el nodoActual (sirve para que en la recursión no vuelva por el eje que conecta a nodoActual con nodoDeDondeVengo)
%  \end{compactitem}
% %  \STATE \COMMENT{n es la cantidad de vértices. arrayEjes un array de listas de ejes (en la i-esima posición del arreglo tiene los ejes que van del i-esimo vertice a los restantes del AG), nodoActual es el nodo para el cual yo voy a recorrer sus ejes en este paso de la recursión, destino el vértice al cual quiero llegar recorriendo el AG para luego calcular el peso y nodoDeDondeVengo es el nodo de donde proviene el nodoActual (sirve para que en la recursión no vuelva por el eje que conecta a nodoActual con nodoDeDondeVengo).}  
%  \FOR {los ejes de la posición \textit{arrayEjes}[\textit{nodoActual}] como \textit{eje} }
%       \IF {\textit{eje} no se conecta con el nodo \textit{nodoDeDondeVengo}}
% 	  \IF {\textit{eje} se conecta con el nodo \textit{destino}}
% 	      \STATE \textit{this}.peso $\leftarrow$ \textit{eje}.peso
% 	      \STATE \textbf{return} true
% 	  \ENDIF
% 	\IF {\textit{eje}.origen == \textit{nodoActual}}
% 	  \IF { calcular\_peso(\textit{n}, \textit{arrayEjes}, \textit{eje}.destino, \textit{destino}, \textit{nodoActual})}
% 	      \IF {\textit{this}.peso $>$ \textit{eje}.peso}
% 		  \STATE \textit{this}.peso $\leftarrow$ \textit{eje}.peso
% 	      \ENDIF
% 	      \STATE \textbf{return} true
% 	  \ENDIF
% 	\ELSE
%       \IF {calcular\_peso(\textit{n}, \textit{arrayEjes}, \textit{eje}.origen, \textit{destino}, \textit{nodoActual})}
% 	  \IF {\textit{this}.peso $>$ \textit{eje}.peso}
% 	      \STATE \textit{this}.peso $\leftarrow$ \textit{eje}.peso
% 	  \ENDIF
% 	  \STATE \textbf{return} true
%       \ENDIF
%       \ENDIF
%       \ENDIF
%  \ENDFOR
%  \STATE \textbf{return} false
% \end{algorithmic}
% Complejidades:
% \begin{compactitem}
% 	\item Todas las asignaciones y comparaciones son O(1).
% 	\item La cantidad total de veces que se va a ingresar al for en la totalidad de las llamadas recursivas tiene complejidad O(n). Esto se debe a lo siguiente:
% 	%\item La cantidad de veces que se ingresa al for es la cantidad de ejes que van del nodoActual hacia otros nodos. Esta cantidad de ejes es como maximo n-1 ya que es la cantidad de ejes necesarios en un grafo de n vertics para formar un arbol generador. Esto se debe a que no llamamos recursivamente sobre el eje del cual venimos (lo evitamos sabiendo el nodoDeDondeVengo) y como no hay ciclos no vamos a recorrer ejes ya recorridos con anterioridad. Vale aclarar que en cada llamada recursiva sobre otro nodo se van a revisar todos los ejes que conectan a este nodo con otros y esto va a incluir al nodo de donde vengo. Finalmente si hago una llamada recursiva por cada nodo (en realidad si tengo n nodos, la cantidad maxima de llamadas es n-2 porque una vez que estoy en un nodo que se conecta con el nodo destino no vuelvo a hacer recursion sobre el nodo destino) voy a estar revisando cada uno de sus ejes que lo conectan con otro nodo
% 	\item La idea en que se recorren los ejes/vertices en este algoritmo sigue la idéa de recorrer un grafo del algoritmo DFS ya que lo que hacemos es recorrer en ``profundidad'' al AG que se genera con los ejes que se encuentran en el arreglo. Lo que vamos a hacer es evitar recorrer el eje por el cual venimos (los if del algoritmo lo evitan) e ir haciendo recursion hasta estar parados en un nodo el cual se conecte con el nodo destino o haber llegado a un nodo que no se conecta con ningun otro nodo(sin contar al nodo de donde vengo). Para el caso en que llegamos a un nodo que se conecta con el nodo destino vamos a retornar ``true'' y vamos a empezar a guardar en ``this.peso'' el peso del eje menos pesado del camino que nos llevo desde el nodo inicial(el origen que fue el primer nodoActual) hasta el nodo destino y en el caso en que no me conecto con ningun otro nodo voy a retornar false para volver al nodo que me llamo con la función recursiva y así irme por otro eje (si es que lo hay) usando la función recursiva.
% 	\item Por lo dicho anteriormente podemos asegurar que la cantidad de veces que se ejecute el for en peor caso es 2(n-1). Este seria el caso en que haya un camino simple de longitud maxima entre el nodo origen y el nodo destino lo que hace que cada vez que ingreso al for en una llamada recursiva voy a recorrer 2 posibles ejes (uno es el eje que me conecta al nodoDeDondeVengo y otro es el eje que me conecta a otro nodo) y esto lo voy a hacer n-1 veces ya que cuando esté parado en el nodo que se conecta con un eje al nodo destino no voy a llamar a la recursion sobre el nodo destino sino que voy a retornar true.
% 	\item Complejidad final O(n) (Se considera necesario que los ejes que se encuentran en el arreglo formen un Árbol generador ya que en caso contrario la función recursiva no termina) .
% \end{compactitem}
% \end{algorithm}


\end{parr}


%
\subsection{Demostración de la solución}
\subsubsection{Demostración de que genera el árbol generador máximo}
\textbf{Demostración de que es generador}: Sea G un grafo conexo y A el subgrafo generado por Kruskal.
\begin{compactenum}
 \item Cada vez que agregamos un eje al árbol primero nos aseguramos que sus extremos no pertenezcan al mismo SET. Es decir, que no agreguemos un eje que una dos vértices de la misma componente conexa. Los sets nos aseguran esto ya que empieza cada vértice perteneciendo a una componente conexa distinta, cada vez que agregamos un eje al árbol unimos los sets de sus dos extremos y sólo se puede aumentar en número de elementos de un set si se lo une con otro. Es decir, el IF de la línea 8 nos asegura de que no estemos uniendo dos vértices de la misma componente conexa y por ende nunca generamos ciclos en A.
 \item 	Nos faltaría ver que es conexo. Asumamos que no entonces en A hay dos o más componentes conexas. Sean A$_1$ y A$_2$ dos componentes conexas. Como G era conexo existe un eje que une a un vértice de A$_1$ y un vértice de A$_2$. Cuando Kruskal iteró a éste eje, la función FIND-SET hubiera dado diferente para sus extremos entonces lo hubiera agregado a A, sin importar qué vértices pertenecían a ambas componentes conexas en ese momento de la ejecución del algoritmo. Podemos asegurar esto porque ambos vértices pertenecerían a componentes conexas diferentes sin importar si a A$_1$ ya le había agregado todos sus vértices finales o no, y lo mismo con A$_2$. Absurdo ya que entonces en la terminación del algoritmo A$_1$ y A$_2$ no serían dos componentes conexas distintas porque los uniría un eje.
\end{compactenum}
\textbf{Demostración de que es máximo}: Probaremos que la proposición ``\textit{si F es el conjunto de ejes elegido en cualquier instancia del algoritmo, entonces hay algún árbol generador máximo que contiene a F}'' por inducción en la longitud de F.
\begin{compactenum}
 \item Caso Base: la lista de ejes elegidos es vacía. Se cumple ya que la lista vacía de ejes está incluída en cualquier árbol generador mínimo.
 \item Paso inductivo: asumamos que la proposición vale para un F no final y sea T un árbol generador mínimo que contiene a F. Si el próximo eje elegido \textit{e} por Kruskal está en T entonces F + \{\textit{e}\}  cumple con la proposición. Si \textit{e} no está en T entonces T + \{\textit{e}\} contiene un ciclo al que pertenece e ya que T era un árbol y \textit{e} no pertenecía a éste. Sea \textit{f} un vértice de ese mismo ciclo con \textit{f} $\neq$ \textit{e}; entonces T - \{\textit{f}\} + \{\textit{e}\} no contiene ciclos y es árbol generador y además tiene el mismo peso que T sino \textit{f} tendría más peso que \textit{e}, pero en ese caso Kruskal hubiera elegido a \textit{f} y no a \textit{e}. Entonces   T - \{\textit{f}\} +\{ \textit{e}\} es un árbol generador máximo y F + \textit{e} está contenido en él.
\end{compactenum}

\subsubsection{Demostración de que el árbol generador máximo nos sirve}
Vamos a demostrar que el camino entre la ciudad origen y la ciudad destino, desde ahora \textbf{p} y \textbf{q} respectivamente, perteneciente al \textit{árbol generador máximo} (A.G.MAX) del grafo \textbf{G} es el que permite mayor peso de transportación para el camión. Si hay sólo un camión entonces ese camino es el mejor, es encontrado por Kruskal y pertenece al árbol.

Sea \textbf{C} el camino entre \textbf{p} y \textbf{q} que obtenemos mediante Kruskal. Vamos a suponer que existe otro camino \textbf{C'} (óptimo) entre \textbf{p} y \textbf{q} tal que 
\begin{equation}
\label{menor_peso} 
m(C') > m(C)  \footnote{Por simplicidad, diremos que la función m(camino) equivale al menor peso de las aristas que son contenidas en el camino.}
\end{equation}

Sea \textbf{e = (v,w)} un eje de \textbf{C'} que no se encuentra en A.G.MAX. Como A.G.MAX es un árbol, existe un único camino simple entre cualquier par de nodos y llamaremos \textbf{K} al camino simple que une \textbf{v} y \textbf{w}. Para que se cumpla [\ref{menor_peso}], tiene que valer que
\begin{equation}
\label{e}
\exists ~  K_{i} \in K, ~~~  m(K_{i}) < m(e)
\end{equation}
ya que sino en lugar de tomar \textbf{e} tomo \textbf{K} y puedo mejorar al óptimo, lo cual sería un absurdo. Pero si vale [\ref{e}] entonces Kruskal en vez de elegir a todos los ejes que forman el camino \textbf{K} hubiera tomado sólo a los que tienen peso mayor y luego a \textbf{e}, el cual no formaría ciclo ya que el camino entre \textbf{v} y \textbf{w} no se llega a formar. Luego como Kruskal no lo eligió, es un absurdo, el cual surge de suponer que hay un camino mejor entre \textbf{p} y \textbf{q} que el resultante de aplicar el algoritmo de Kruskal.

%Vamos a demostrar que el camino entre la ciudad origen y la ciudad destino, desde ahora \textbf{p} y \textbf{q} respectivamente, perteneciente al \textit{árbol generador máximo} (A.G.MAX) es el que permite mayor peso de transportación para el camión. Si hay sólo un camino entonces ese camino es el mejor y es encontrado por Kruskal y pertenece al árbol.
%
%Asumamos entonces que hay dos o más caminos. Sean P$_1$ y P$_2$ dos caminos entre \textit{p} y \textit{q}. Queremos ver que si P$_1$ es el camino perteneciente al A.G.MAX y P$_2$ otro camino cualquiera entre p y q del grafo original, entonces el eje con mínimo peso de P$_1$ tiene mayor o igual peso al eje con mínimo peso de P$_2$. Matemáticamente:
%\begin{center}
%	Sean P$_1$ y P$_2$ dos caminos con origen \textbf{p} y destino \textbf{q}, P$_1$ el camino perteneciente al A.G.MAX, P$_2$ otro camino, e$_1$ el eje con menor peso en P$_1$ y e$_2$ el eje con menor peso en P$_2$, entonces peso(e$_1$) $\geq$ peso(e$_2$)
%\end{center}
%Para demostrarlo asumamos lo contrario. Es decir:
%\begin{center}
%	($\exists$ P$_2$) min\{w : w $\in$ P$_2$\} $>$ min\{w : w $\in$ P$_1$\}
%\end{center}
%Sea e$_1$ el eje con mínimo peso en P$_1$, e$_2$ lo propio con P$_2$ y \texttt{A} el A.G.MAX generado. Sea \texttt{A}+\{e$_2$\} el árbol generador máximo más el eje e$_2$. Entonces, en este nuevo grafo hay un sólo ciclo y e$_2$ pertenece a ese ciclo. Si e$_1$ pertenece al mismo ciclo entonces llegamos a un absurdo porque el árbol \texttt{A}+\{e$_2$\}-\{e$_1$\} tiene mayor suma de pesos que \texttt{A} y además también es árbol generador.
%
%Entonces, e$_1$ no pertence al mismo ciclo que e$_2$ en \texttt{A}+\{e$_2$\}.
% sería un bosque con dos componentes conexas. Si e$_2$ tiene extremos en ambas componentes conexas entonces llegamos a un absurdo ya que A-\{e$_1$\}+\{e$_2$\} sería un árbol generador con mayor suma de pesos que \texttt{A}.

% Entonces, ambos extremos de e$_2$ pertenecen a una misma componente conexa de \texttt{A}-\{e$_1$\}. 




\subsection{Complejidad (modelo uniforme)}
%Como podremos ver en el análisis de ambos algoritmos, el constructor del grafo y el BFS-mod, la complejidad sería $\theta\left(\vert cantidad de amistades \vert * cantidad de investigadores\right)$ y $\theta\left(\vert cantidad de amistades \vert + cantidad de investigadores\right)$ respectivamente. Esto se debe a que son las mayores complejidades de las líneas de su ejecución y hacen despreciables a las demás. Finalmente la complejidad del constructor haría lo mismo con la del BFS-mod ya que crece mucho más rápido dejando como complejidad final a $\theta\left(\vert l \vert * cantidad de investigadores\right)$. No consideramos que haya un peor caso ya que el constructor siempre hará lo mismo, la misma ejecución, sin importar las características de los investigadores y/o sus amistades entre sí. Podemos decir tal afirmación ya que no hay \textit{ifs} que hagan diferir de forma considerable la complejidad dependiendo del resultado de la guarda de estos y los \textit{fors} tienen un tiempo de ejecución fijo.
%
%Esto parecería raro a primera vista, ya que la complejidad de la parte ``interesante'' del algoritmo es mucho menor que algo que parecería trivial. El problema es que aunque lo parezca no era trivial. No teníamos asegurado el orden de los vértices en la entrada ya que recibíamos los ejes en una lista de adyacencia. Además, no podíamos asegurar que no vengan repetidos y en muchos casos seguro que vendrían repetidos.
%
%Aun así, la complejidad cumple con el máximo pedido por la cátedra.
%
Si recordamos cómo actúa nuestro algoritmo principal:
\begin{compactenum}
	\item Leer de la entrada el origen y el destino; y la lista de adyacencias (las rutas).
	\item Pasar la lista de strings y peso a lista de IDs (enteros) y peso. Ordenarla en orden descendente.
	\item Generar el árbol generador máximo en base a la lista generada.
	\item Buscar la cantidad máxima de mercadería a transportar en base al grafo generador máximo y el origen y el destino.
\end{compactenum}
\noindent A la parte \textbf{1} la hacemos en O(m) ya que es simplemente iterar los ejes y pasarlos a una lista.

A la parte \textbf{2} la hacemos en O(m log n) ya que es la funcionalidad que cumple \textit{mapearAVértices}. Esta complejidad se cumple siempre ya que no importa cuál sea el vector de entrada, la función va a tener que iterarlo completamente e ir guardándose los vértices para después pasarlos a un set y después identificar uno a uno con un entero a las ciudades de entrada. Siempre va a tomar tiempo O(m log n) sin importar las características de la lista de rutas.

A la parte \textbf{3} la hacemos en O(m $\alpha$(n)), con  $\alpha$(n) siendo la inversa de Ackerman ya que el algoritmo es exactamente igual que el visto en clase, siendo la única diferencia el orden de la lista pero esto es irrelevante para la complejidad ya que Kruskal siempre iterará la lista de izquierda a derecha. El peor caso consistiría en que el algoritmo itere todos los ejes de la lista de adyacencias antes de encontrar un árbol generador máximo lo que implicaría complejidad O(n$^{2}\alpha$(n)). El mejor caso sería que solamente tenga que iterar los primeros \textbf{n-1} ejes y ya encuentre la solución, entonces su complejidad sería O(n$\alpha$(n)). 

A la parte \textbf{4} la hacemos en O(n) en peor caso ya que por un lado es la complejidad de \textit{calcular\_peso\_camino\_maximo}. Además esta función llama a la función \textit{calcular\_peso} que funciona de la siguiente manera:

La idea en que se recorren los ejes/vertices en este algoritmo sigue la idéa de recorrer un grafo del algoritmo DFS ya que lo que hacemos es recorrer en ``profundidad'' al AG que se genera con los ejes que se encuentran en el arreglo. Lo que vamos a hacer es evitar recorrer el eje por el cual venimos (los if del algoritmo lo evitan) e ir haciendo recursion hasta estar parados en un nodo el cual se conecte con el nodo destino o haber llegado a un nodo que no se conecta con ningun otro nodo(sin contar al nodo de donde vengo). Para el caso en que llegamos a un nodo que se conecta con el nodo destino vamos a retornar ``true'' y vamos a empezar a guardar en ``peso\_global'' el peso del eje menos pesado del camino que nos llevo desde el nodo inicial(el origen que fue el primer nodoActual) hasta el nodo destino y en el caso en que no me conecto con ningun otro nodo voy a retornar false para volver al nodo que me llamo con la función recursiva y así irme por otro eje (si es que lo hay) usando la función recursiva.

Por lo dicho anteriormente podemos asegurar que la cantidad de veces que se ejecute el for en peor caso es 2(n-1). Este seria el caso en que haya un camino simple de longitud maxima entre el nodo \textit{origen} y el nodo \textit{destino} lo que hace que cada vez que ingreso al for en una llamada recursiva voy a recorrer 2 posibles ejes (uno es el eje que me conecta al \textit{nodoDeDondeVengo} y otro es el eje que me conecta a otro nodo) y esto lo voy a hacer n-1 veces ya que cuando esté parado en el nodo que se conecta con un eje al nodo \textit{destino} no voy a llamar a la recursion sobre el nodo \textit{destino} sino que voy a retornar \textit{true}. El peor caso sería que \textit{p} y \textit{q} sean adyacentes y tomaría complejidad O(1) ya que tiene que iterar sólo un eje.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tests}
Como dijimos antes, la complejidad del algoritmo depende mucho de la complejidad de \textit{mapearAVértices} ya que es de las funciones con \textit{peor} peor caso pero además siempre tarda en el mismo orden asintótico, a diferencia de \textit{Kruskal} que su mejor caso es diferente de su caso promedio y peor caso, aunque su peor caso sea asintóticamente igual al de  \textit{mapearAVértices}. Debido a esto decidimos analizar detenidamente 4 casos:
\begin{compactitem}
	\item \textbf{Grafo completo}: las ciudades están unidas todas entre sí.
	\item \textbf{Grafo disperso}: la cantidad de rutas es igual a \textbf{30/100 por n * (n - 1) / 2}. O sea, el 30\% de los ejes que tendría un completo de ese tamaño. Decidimos el 30\% porque para grafos con un n no demasiado grande se podría seguir considerando disperso.	Estamos al tanto que el crecimiento de la cantidad de ejes es cuadrático y por esto no es la mejor idea elegir un porcentaje porque en los ``números grandes'' la diferencia entre este test y el completo será despreciable. Pero para el caso que nos concierne, la diferencia será por lo menos apreciable
	\item \textbf{Árbol}: las cantidad de rutas es igual a \textbf{(n - 1)}
	\item \textbf{``Peor Caso''}: el algoritmo recibe como entrada un grafo completo tal que es el peor caso para \textit{Kruskal} y \textit{calcular\_peso\_camino\_máximo} al mismo tiempo. Lo que hicimos fue:
	\begin{compactitem}
	      \item Para que sea el peor caso de \textit{calcular\_peso\_camino\_máximo}: el peor caso sería que la función tenga que recorrer todos los ejes del árbol generador máximo para encontrar la solución. Entonces hacemos que el árbol generador máximo sea un ``camino'' y \textbf{p} y \textbf{q}  sean los extremos de ese camino. Por claridad tomemos que \textbf{p} es el principio y \textbf{q} el final del camino.
	      \item Para que sea el peor caso de \textit{Kruskal}: lo que queremos es que alcance a iterar todos los ejes del grafo antes de encontrar un árbol generador y terminar. Para esto nos teníamos que asegurar que sí o sí tenga que poner el eje de menor peso. Entonces dividimos al conjunto de ejes en 4 partes de la siguiente manera:
		  \begin{compactitem}
		    \item Si es \textit{e} un eje del camino resultante en el árbol generador máximo y este eje no tiene como extremo a \textbf{q} (final del camino), que le ponga el peso máximo (en este caso entre 2000 y 2500):
		    \begin{center}
			2000 $\leq$ peso(\textit{e}) $\leq$ 2500
		    \end{center}
		    \item Si \textit{e} no es un eje del camino resultante y no tiene a \textbf{q} como extremo, que le ponga peso medio alto (en este caso entre 500 y 1999):
		    \begin{center}
			500 $\leq$ peso(\textit{e}) $\leq$ 1999
		    \end{center}
		    \item Si \textit{e} es \textbf{el} eje que tiene como extremo a \textbf{q} y es del camino, que le ponga uno más que el máximo bajo (en este caso 499):
		    \begin{center}
			peso(\textit{e}) $=$ 499
		    \end{center}
		    \item Si \textit{e} es un eje que tiene como extremo a \textbf{q} y no es del camino, que le ponga medio bajo (en este caso entre 100 y 498):
		    \begin{center}
			100 $\leq$ peso(\textit{e}) $\leq$ 498
		    \end{center}
		  \end{compactitem}
	\end{compactitem}
	      De este modo, los ejes pertenecientes al árbol generador resultante van a quedar primeros en la lista de adyacencias ordenada. Además, no forman ciclos entre ellos ya que forman un camino. Por ende, Kruskal los va a agregar y el próximo eje a iterar de la lista es el que une a \textbf{q} con el \textbf{penúltimo vértice} del camino resultante (de nuevo, tomando a q como el final del camino).\\
	      No alcanzará a iterar los n-2 ejes restantes que tienen como extremo a \textbf{q} ya que agregará a \textbf{q} al árbol resultante y terminará; pero igual itera a todos los ejes de todos los otros vértices, lo suficiente para que sea el peor caso de Kruskal. Por su parte, \textit{calcular\_peso\_camino\_máximo} iterará a todos los ejes del árbol generador máximo ya que éste es un camino y tiene a \textbf{p} y a \textbf{q} como extremos.
\end{compactitem}

\ \\
En otras palabras, fijamos el m (cant amistades) y fuimos variando el n (cantidad investigadores). Entonces tomamos a m como tamaño de entrada y calculamos cuánto valdría n para cada uno de los casos de tests.

Para calcular la \textit{complejidad empírica} decidimos contar la cantidad de operaciones básicas del algoritmo completo y las de  Kruskal, mapearAVértices y calcular\_peso\_camino\_máximo cada uno por separado. Para ello nos guardamos 4 contadores y a cada uno le sumábamos uno si se ejecutaba una operación básica en su \textit{sección de ejecución respectiva} y si usábamos funciones provistas por Java que no fuesen de tiempo constante, le sumábamos al contador su complejidad asintótica. Por ejemplo, ordenar lleva tiempo O(n log n) según la documentación de java; por ende, le sumaríamos n*log(n) al contador.

Ya que en los 4 casos la complejidad será siempre la misma debido a que \textit{mapearAVértices} influye a las demás, decidimos además de analizar los casos para las variables juntas y separadas; también analizar a Kruskal y calcular\_peso\_camino\_máximo juntos para \textit{Peor Caso} y \textit{Grafo Completo}. De esta forma, se puede apreciar con más detenimiento los valores de estas dos funciones sin ser ofuscadas por \textit{mapearAVértices} y la suma de las 3.

Valores de n para los diferentes casos (recordar que m está fijo y por eso podemos conseguir al n):
\begin{compactitem}
 \item Grafo Completo: ``n = $\tfrac{1+\sqrt{1+8m}}{2}$'' usando la ecuación ``m = $\tfrac{n(n-1)}{2}$''
 \item Grafo Disperso: ``n = $\tfrac{3+\sqrt{9+240m}}{6}$'' usando la ecuación ``m = 30\% $\tfrac{n(n-1)}{2}$''
 \item Grafo Árbol: ``n = m+1'' usando la ecuación ``m = n-1''
 \item Peor Caso: ídem grafo completo
\end{compactitem}

\subsection{Gráficos}
%
\begin{figure}[H]
\centering
\epsfig{file=./graficos/Ej1/arbol.pdf,width=0.9\linewidth,clip=}
\caption{Tests para grafos completos.}
\end{figure}



\begin{figure}[H]
\centering
\epsfig{file=./graficos/Ej1/disperso.pdf,width=0.9\linewidth,clip=}
\caption{Tests para grafos dispersos.}
\end{figure}

\begin{figure}[H]
\centering
\epsfig{file=./graficos/Ej1/peorcaso.pdf,width=0.9\linewidth,clip=}
\caption{Tests para Peor Caso.}
\end{figure}

\begin{figure}[H]
\centering
\epsfig{file=./graficos/Ej1/completo.pdf,width=0.9\linewidth,clip=}
\caption{Tests para árboles.}
\end{figure}

Como fue previsto, pudimos acotar el crecimiento de la complejidad empírica de nuestro algoritmo por la complejidad teórica en cada uno de los casos. Recordar que el \textbf{n} es diferente entre los diferentes gráficos y decidimos poner directamente n en la layenda de la función en vez de su valor en base a m para que quede más claro. En todo caso, si se necesita saber el valor de n para los grafos dispersos, por ejemplo, se puede acudir a la sección Tests donde están todas las equivalencias.

Tener cuidado y tener en cuenta que las escalas son diferentes ya que las mediciones cambian mucho, por ejemplo, entre el test de árboles y los demás. Esto se debe, claramente, a que la cantidad de ejes en los árboles es mucho menor que en los otros tests y por ende el valor de la ecuación ``m log n'' es mucho menor para el mismo m. Esto igual implica que la diferencia entre las distintas funciones es menor en escala y por ende se puede apreciar con mayor claridad los valores de éstas. En el resto de las funciones los valores de las funciones \textit{mapearAVértices} y la suma de los tres es tan grande que en el gráfico se tiene que menospreciar la diferencia entre las funciones restantes para poder graficar a todas en un mismo gráfico.

Notar, además que en el caso de todos los gráficos menos el de Peor Caso, la diferencia entre \textit{mapearAVértices} y la suma de las 3 es muy chica, pero igual apreciable. En cambio, en el caso de Peor Caso, hay una diferencia muy notable entre estas 2 mediciones y esto se debe a que la complejidad de \textit{Kruskal} ahora tiene mucha influencia sobre la suma de las 3. No es tanto el caso de calcular\_peso\_camino\_máximo ya que aunque es su peor caso, su complejidad O(n) lo hace poco influyente. Para más claridad entre estas dos y el peor caso, tenemos el siguiente gráfico:

\begin{figure}[H]
\centering
\epsfig{file=./graficos/Ej1/krusk-y-calc.pdf,width=0.9\linewidth,clip=}
\caption{Tests para grafos completos y Peor Caso sólo de Kruskal y calcular\_peso\_camino\_máximo.}
\end{figure}


%
%Lo más remarcable es la diferencia del gráfico de árboles con los otros 2. Claramente toma tiempo mucho menor ... acaso no es un mejor caso, y por ende, los otros dos son peor caso? En verdad esto se debe a que el tamaño de entrada del caso de los árboles es MUCHO menor ya que es tanta la diferencia de ejes que el gráfico miente. La complejidad sigue siendo la misma pero el m es mucho más chico y multiplica menos la cantidad de ejecuciones; a eso se debe esta ``peculiaridad''. O sea, estamos comparando diferentes tamaños de entrada, básicamente, entre los 3 grafos. La idea era remarcar que no importa la familia, nuestro algoritmo trabajaría en un tiempo que podía ser acotado por nuestra complejidad teórica.
%
%Aun así, nos sirve el gráfico de árboles ya que como los valores no son tan altos podemos apreciar mejor la diferencia entre los 3 sub-casos que dependían si p y/o q estaban o no. Podemos observar, por curiosidad simplemente porque esto excede a lo pedido, que en el caso de que ambos están es un poco mayor a los otros 2 casos. Esto simplemente es porque los otros 2 casos \textbf{no} ejecutan el algoritmo de BFS-mod porque antes de entrar preguntan si es necesario, o sea, si ambos p y q pertenecen a los investigadores. Si alguno de los 2 no está, devolvería 0 simplemente. En cambio, cuando ambos están sí o sí debería ejecutar el algoritmo de BFS-mod para encontrar la longitud del camino mínimo.
%
\subsection{Conclusiones}
En conclusión, el ejercicio nos pareció interesante porque aunque parecía simple a simple vista (valga la redundancia), debimos usar 4 funciones separadas y lo suficientemente complejas como para que sea necesario incluír su pseudocódigo en el informe: \textit{mapearAVértices}, \textit{Kruskal}, \textit{calcular\_peso\_camino\_máximo} y \textit{calcular\_peso}.

Además, los gráficos fueron interesantes ya que de nuevo, como en el ejercicio uno, la complejidad estaba \textbf{influenciada} por la función que aparentaba ser la menos importante, en este caso \textbf{mapearAVértices} que simplemente parseaba los \texttt{Strings} para que \textit{Kruskal} pudiera funcionar de forma adecuada.

%
%
%
